// 239 hard 滑动窗口最大值

// 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
// 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
// 返回滑动窗口中的最大值。
//
//
// 示例:
// 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
// 输出: [3,3,5,5,6,7]
// 解释:
//
//   滑动窗口的位置                最大值
// ---------------               -----
// [1  3  -1] -3  5  3  6  7       3
//  1 [3  -1  -3] 5  3  6  7       3
//  1  3 [-1  -3  5] 3  6  7       5
//  1  3  -1 [-3  5  3] 6  7       5
//  1  3  -1  -3 [5  3  6] 7       6
//  1  3  -1  -3  5 [3  6  7]      7
//  
//
// 提示：
// 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
//
// 进阶：
// 你能在线性时间复杂度内解决此题吗？


// 如果求窗口最大值，用单调递减队列；反之，单调递增数列
var maxSlidingWindow = function(nums, k) {
    if (!nums.length) return [];
    if (k === 1) return nums;

    // 维护一个单调队列。双端队列，既可以从队首出队，又可以从队尾删除
    let queue = [];
    let res = [];
    for(let i = 0; i< nums.length; i++){
        // 过老的，已不再窗口范围的，从队首剔除
        if (queue.length && i - k + 1 > queue[0]) queue.shift();
        // 新入队元素，不符合递减规则，从队尾挨个踢除过小元素。（为了保持新元素入队列后，队列的单调性）
        while(queue.length && nums[queue[queue.length - 1]] <= nums[i])queue.pop();
        queue.push(i);
        // 队首元素即为最大，输出元素
        if(i >= k - 1) res.push(nums[queue[0]]);
    }
    return res;
};

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7],
    3))